package 中等.图.dijkstra;

import java.util.Arrays;

/**
 * 你在一个路口里，路口由 n 个路口组成，路口编号为 0 到 n - 1 ，某
 * 些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意
 * 路口，且任意两个路口之间最多有一条路。
 * 给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei]
 * 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知
 * 道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
 * 请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。
 *
 * @ https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/description/?envType=daily-question&envId=2024-03-05
 * @date 2024/03/06
 */
public class 到达目的地的方案数_1976 {
    public static void main(String[] args) {

        //[]
        到达目的地的方案数_1976 impl = new 到达目的地的方案数_1976();

        System.out.println(impl.countPaths(7, new int[][]{
                {0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3}, {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}
        }));

    }

    /**
     * 迪杰斯特拉算法+动态规划
     * 1，定义：
     * 定义 g[i][j] 表示从路口 i 到路口 j 的花费 time，如果没有道路，那么为无穷大
     * 定义 dis[i] 为路口 0 到路口 i 的最短距离是多少，dis[0] = 0，从路口 0 到
     * 路口 0 的最短距离为 0，到其他路口最短距离初始化为无穷大
     * 2，算法步骤：
     * a. 从 dis[i] 中选取一个未被选取过的路口 i 且到路口 0 道路是最短的
     * b. 遍历路口 i 可以到达哪些路口，如果 dis[i] + g[i][j] < dis[j]
     * 那么更新 dis[j] 的值为 dis[i] + g[i][j]
     * 3，动态规划求 花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数
     * a. 定义 dp[i] 表示从路口 0 出发到达路口 i 花费最少时间的方案数
     * b. dp[0] = 1 从 0 到 0 的方案数始终为 1
     * 如果 dis[i] + g[i][j] < dis[j] 那么 dp[j] = dp[i]
     * 如果 dis[i] + g[i][j] = dis[j] 那么 dp[j] = dp[j] + dp[i]
     */
    public int countPaths(int n, int[][] roads) {
        // 邻接矩阵
        long[][] gird = new long[n][n];
        for (long[] row : gird) {
            Arrays.fill(row, Long.MAX_VALUE / 2);
        }
        for (int[] road : roads) {
            gird[road[0]][road[1]] = road[2];
            gird[road[1]][road[0]] = road[2];
        }
        long[] dis = new long[n];
        Arrays.fill(dis, 1, n, Long.MAX_VALUE / 2);

        long[] dp = new long[n];
        dp[0] = 1;
        boolean[] visited = new boolean[n];

        while (true) {
            int i = getMinDis(dis, visited);
            if (i == n - 1) {
                // 不可能找到比 dis[n-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
                return (int) dp[n - 1];
            }
            visited[i] = true;

            for (int j = 0; j < n; j++) {
                long newDis = dis[i] + gird[i][j];
                if (newDis < dis[j]) {
                    dis[j] = newDis;
                    dp[j] = dp[i];
                } else if (newDis == dis[j]) {
                    dp[j] = dp[j] + dp[i];
                    dp[j] %= 1000000007;
                }
            }
        }
    }

    private int getMinDis(long[] dis, boolean[] visited) {
        int idx = -1;
        for (int i = 0; i < dis.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (idx == -1 || dis[i] < dis[idx]) {
                idx = i;
            }
        }
        return idx;
    }

}
